We study the problem of estimating a low-rank positive semidefinite (PSD)matrix from a set of rank-one measurements using sensing vectors composed ofi.i.d. standard Gaussian entries, which are possibly corrupted by arbitraryoutliers. This problem arises from applications such as phase retrieval,covariance sketching, quantum space tomography, and power spectrum estimation.We first propose a convex optimization algorithm that seeks the PSD matrix withthe minimum $\ell_1$-norm of the observation residual. The advantage of ouralgorithm is that it is free of parameters, therefore eliminating the need fortuning parameters and allowing easy implementations. We establish that withhigh probability, a low-rank PSD matrix can be exactly recovered as soon as thenumber of measurements is large enough, even when a fraction of themeasurements are corrupted by outliers with arbitrary magnitudes. Moreover, therecovery is also stable against bounded noise. With the additional informationof an upper bound of the rank of the PSD matrix, we propose another non-convexalgorithm based on subgradient descent that demonstrates excellent empiricalperformance in terms of computational efficiency and accuracy.
展开▼